#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        map<int, int> hash;

        for (auto e : nums) hash[e]++;

        vector<int> select, disselect;

        int res = 0, cur = -1, index = 0;;
        for (auto pair : hash)
        {
            int key = pair.first, value = (pair.second * pair.first);
            int sct;

            if (key == (cur + 1) && index > 1)
                sct = max(select[index - 2], disselect[index - 1]) + value;
            else if (key != (cur + 1) && index > 0)
                sct = max(select[index - 1], disselect[index - 1]) + value;
            else
                sct = value;

            int dis = index > 0 ? max(select[index - 1], disselect[index - 1]) : 0;

            select.push_back(sct);
            disselect.push_back(dis);

            cur = key;
            ++index;
        }
        return max(select.back(), disselect.back());
    }
};